package com.sj.排序算法;

import java.util.Arrays;

/**
 * @author sj
 * @date 2021/5/3
 **/
public class 计数排序 {

    // 计数排序(Java)
        public static void main(String[] argv) {
            int[] A = 计数排序.countingSort(new int[]{ 9, 3, 2, 8, 1});
            System.out.println(Arrays.toString(A));
        }
        public static int[] countingSort(int[] A) {
            int[] B = new int[A.length];
            // 假设A中的数据a'有，0<=a' && a' < k并且k=100
            int k = 10;
            countingSort(A, B, k);
            return B;
        }
        private static void countingSort(int[] A, int[] B, int k) {
            int[] C = new int[k];
            // 计数
            for (int j = 0; j < A.length; j++) {
                int a = A[j];
                C[a] += 1;
            }
            System.out.println(Arrays.toString(C));
            // 求计数和
            for (int i = 1; i < k; i++) {
                C[i] = C[i] + C[i - 1];
            }
            System.out.println(Arrays.toString(C));
            // 整理
            for (int j = A.length - 1; j >= 0; j--) {
                int a = A[j];
                B[C[a] - 1] = a;
                C[a] -= 1;
            }
        }

}
